package codeRandomThoughts.Test496下一个更大元素I;

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //用于保存nums2的每个元素的下一个更大元素的数值
        int[] nextGreater = new int[nums2.length];
        //初始化为-1;
        Arrays.fill(nextGreater, -1);

        //单调递增栈 从栈顶到栈底递增
        Stack<Integer> monotonicStack = new Stack<>();

        for (int i = 0; i < nums2.length; i++) {
            while (!monotonicStack.isEmpty() && nums2[monotonicStack.peek()] < nums2[i]) {
                Integer pop = monotonicStack.pop();
                nextGreater[pop] = nums2[i];
            }

            //放入下标
            monotonicStack.push(i);
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {
                    result[i] = nextGreater[j];
                }
            }
        }

        return result;
    }
}
